|
In mathematics, a Golomb ruler is a set of marks at integer positions along an imaginary ruler such that no two pairs of marks are the same distance apart. The number of marks on the ruler is its ''order'', and the largest distance between two of its marks is its ''length''. Translation and reflection of a Golomb ruler are considered trivial, so the smallest mark is customarily put at 0 and the next mark at the smaller of its two possible values. The Golomb ruler was named for Solomon W. Golomb and discovered independently by and . Sophie Piccard also published early research on these sets, in 1939, stating as a theorem the claim that two Golomb rulers with the same distance set must be congruent. This turned out to be false for six-point rulers, but true otherwise.〔.〕 There is no requirement that a Golomb ruler be able to measure ''all'' distances up to its length, but if it does, it is called a ''perfect'' Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more marks.〔 A Golomb ruler is ''optimal'' if no shorter Golomb ruler of the same order exists. Creating Golomb rulers is easy, but finding the optimal Golomb ruler (or rulers) for a specified order is computationally very challenging. Distributed.net has completed distributed massively parallel searches for optimal order-24 through order-27 Golomb rulers, each time confirming the suspected candidate ruler.〔 〕〔 〕〔 〕〔 〕 In February 2014, distributed.net began the search to find optimal Golomb rulers (''OGRs'') of order-28. Currently, the complexity of finding OGRs of arbitrary order ''n'' (where ''n'' is given in unary) is unknown. In the past there was some speculation that it is an NP-hard problem. Problems related to the construction of Golomb Rulers are provably shown to be NP-hard, where it is also noted that no known NP-complete problem has similar flavor to finding Golomb Rulers. ==Definitions== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Golomb ruler」の詳細全文を読む スポンサード リンク
|